#ifndef __grafo__
#define __grafo__

#include <set>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint;
typedef vector<uint> vuint;

class Grafo {
	protected:
		set<uint> nodos;
		uint *grados;
		vector<vuint> vecinos;
		uint cantNodos;

	public:

		vector<vector<bool> > adyacencia;

		//Crea un grafo dada su cantidad de nodos.
		Grafo (uint cant) {
			vecinos = vector<vuint>(cant);
			adyacencia = vector<vector<bool> >(cant, vector<bool>(cant, false));
			grados = new uint[cant];
			cantNodos = cant;
			
			for (int i = 1; i <= cant; i++) {
				nodos.insert(i);
				grados[i-1] = 0;
			}
		}
		
		//Devuelve la cantidad de nodos
		uint cantidadNodos() const {
			return cantNodos;
		}
		
		//Devuelve los nodos
		set<uint> conjuntoNodos() const {
			return nodos;
		}
		
		//Indica si dos nodos son vecinos
		bool sonVecinos(uint v, uint w) {
			return adyacencia[v-1][w-1];
		}

		//Agrega una arista no dirigida entre inicio y fin.
		void agregarArista(uint inicio, uint fin) {
			vecinos[inicio-1].push_back(fin);
			vecinos[fin-1].push_back(inicio);
			adyacencia[inicio-1][fin-1] = true;
			adyacencia[fin-1][inicio-1] = true;
			grados[inicio-1]++;
			grados[fin-1]++;
		}

		//Devuelve los vecinos de un nodo.
		const vuint& vecindad(uint nodo) const {
			return vecinos[nodo-1];
		}
		
		//Indica los grados de un nodo.
		uint miGrado(uint nodo) const {
			return grados[nodo-1];
		}
		
		//Devuelve los nodos adyacentes al nodo v en P (VERSION MATRIZ)
		//~ set<uint> adyacentes(uint nodo, set<uint> &P) const {
			//~ set<uint> A;
			//~ for(int i = nodo; i < cantNodos; i++) {
				//~ if(adyacencia[nodo-1][i] == true)
					//~ A.insert(i+1);
			//~ }
//~ 
			//~ set<uint> interseccion;
			//~ set_intersection(A.begin(), A.end(), P.begin(), P.end(), inserter(interseccion, interseccion.begin()));
			//~ 
			//~ return interseccion;
		//~ }
		
		//Devuelve los nodos adyacentes al nodo v en P (VERSION LISTA)
		set<uint> adyacentes(uint nodo, set<uint> &P) const {
			set<uint> A;
			uint cant = vecinos[nodo-1].size();
			for(int i = 0; i < cant; i++) {
				if(vecinos[nodo-1][i] > nodo)
					A.insert(vecinos[nodo-1][i]);
			}

			set<uint> interseccion;
			set_intersection(A.begin(), A.end(), P.begin(), P.end(), inserter(interseccion, interseccion.begin()));
			
			return interseccion;
		}
};

#endif
